The proliferation of lightweight, portable computing devices and high-speed wireless local area networks (LANs) has enabled users to remain connected and compute while on the move inside buildings and on campus areas around buildings. This new paradigm has given birth to a new class of applications that are “location aware.” The goal of mobile computing in many instances is to enable a user to interact effectively with his or her physical surroundings. One example of such an interaction is to find a fixed network resource that is nearest to a mobile computing unit so that the user of the mobile computing unit may interact with the fixed network resource.
A key distinguishing feature of these systems is that the application information and/or interface presented to the user is, in general, a function of his or her physical location. The granularity of location information needed may vary from one application to another. For example, locating a nearby printer requires fairly coarse-grained location information whereas locating a book in a library would require fine-grained information.
One component of these systems is the actual tracking system, which determines a user's location. For example, one such system is the Global Positioning System (GPS), which provides inexpensive and portable devices that can locate and track users. Such systems currently are used to provide direction to drivers through an in-vehicle system, provide location and tracking information for marine navigation, and allow shipping companies to locate and track individual shipments. However, the GPS system relies on an unobstructed view of several satellites, making its use for tracking users who are indoors ineffective.
To overcome this obstacle, alternate technologies have been developed to locate and track users or objects in an indoor environment. One such system uses tags placed on the items that are to be tracked. In an electronic sense, the tags can be either active or passive, and they communicate with base stations. The base stations are physically linked together through a wired or wireless network. Each tag transmits a unique code to identify itself. The location of the tag can thereby be determined to be in the vicinity of the base station with which the tag last communicated.
Such tag-based tracking and location systems require a significant installation of specialized base stations. A tag-based system can only determine the location of the tags as being “near” a particular base station. As a result, a large number of base stations must be installed to achieve a sufficiently high resolution. Furthermore, obtrusive tags have to be placed on every item that is to be tracked or located, and in the case of infrared tags, the system operates only when there is a line of sight between the tag and a base station. For these reasons, tag-based systems have shown very limited success.
Another technology has been developed which uses radio frequency transmissions from base stations and mobile units to track the location of mobile units. This technology is described in U.S. patent application Ser. No. 09/513,155, entitled “Using a Derived Table of Signal Strength Data to Locate and Track a User In a Wireless Network, and in U.S. patent application Ser. No. 09/513,355, entitled “Locating and Tracking a User in a Wireless Network Through Environmentally Profiled Data.”
In this system, a Wireless Local Area Network (WLAN) is utilized for locating and tracking users. A WLAN consists of base stations connected to a wired network, and mobile devices that are “connected” to the WLAN through radio frequency signals with the base stations. The signal sensing ability of both the base station and the mobile device are used to determine the location of the mobile device, and thus the location of the user of the mobile device. Specifically, the strength of the received signal from several base stations is measured by the mobile device. The mobile device then compares the signal strength from each of the base stations to a pre-computed table containing the base stations' signal strength at various known locations of the mobile device. From this comparison, the mobile device determines its location. Alternatively, the strength of the signal received from the mobile device can be measured at a number of base stations. This signal strength is then compared by a central computer to a pre-computed table containing the mobile computer's signal strength at the base stations for various known locations. From this table, the central computer determines the location of the mobile computer.
Such a system contains system resources that have a relatively fixed location. Examples of fixed network resources include, but are not limited to, access points, printers, copiers, scanners, office locations, etc. When a mobile user desires to find one such fixed resource, the user submits a query to the system for the location of such a fixed resource. The system determines the location of the user and then searches a database on a system server that contains the location and operational properties of each fixed resource. When an appropriate fixed resource is found, the information regarding the resource is returned to the user.
The classical way to store database records of fixed resources in a system server is to store the records according to a network address and/or capabilities of the fixed resource. Because such systems can be very large, there may be several hundred or thousand records in a resource database that contains information on every fixed resource in the system. The processing overhead required to process a query for the nearest fixed resource of a certain type and having certain properties can be extremely high because the search for a location as very inefficient.